home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / NTUMIN10.ARJ / CAMPG.C < prev    next >
C/C++ Source or Header  |  1992-03-09  |  18KB  |  528 lines
  1. /****************************************************************************
  2.  *
  3.  *      Program name : CAMPG.C
  4.  *
  5.  *      This is the actual minimization algorithm. Variation from the actual
  6.  *    CAMP algorithm is as follows:
  7.  *        1.    Minterms with adjacency 0 or 1 is minimised first
  8.  *        2.    Select next minterm with lowest adjacency wrt b-array
  9.  *        3.  If more than 1 such minterms, select one with the lowest
  10.  *            adjacency wrt to a-array
  11.  *        4.    To shrink the CPT, select an adjacent term, mi that has the
  12.  *            largest wi AND is already covered
  13.  *        5.  If more than one such adjacent terms are covered, select one
  14.  *        with the lowest adjacency wrt to b-array
  15.  *          6.  If more than one such adjacenct terms with lowest adjacency,
  16.  *        select one that could cover most of the uncovered minterms
  17.  *        if chosen to shrink away
  18.  *        7.  If non of the adjacent term is covered (see step 4), select
  19.  *        one with the lowest adjacency wrt b-array from the
  20.  *        uncovered adj term at step 4.
  21.  *
  22.  * --------------------------------------------------------------------------
  23.  *    Copyright (c) 1992. All Rights Reserved. Nanyang Technological
  24.  *    University.
  25.  *
  26.  *    You are free to use, copy and distribute this software and its
  27.  *    documentation providing that:
  28.  *
  29.  *        NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
  30.  *
  31.  *        IT IS NOT MODIFIED IN ANY WAY.
  32.  *
  33.  *        THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
  34.  *
  35.  *    This program is provided "AS IS" without any warranty, expressed or
  36.  *    implied, including but not limited to fitness for any particular
  37.  *    purpose.
  38.  *
  39.  *    If you find NTUMIN fast, easy, and useful, a note or comment would be
  40.  *    appreciated. Please send to:
  41.  *
  42.  *        Boon-Tiong Tan or Othman Bin Ahmad
  43.  *        School of EEE
  44.  *        Nanyang Technological University
  45.  *        Nanyang Avenue
  46.  *        Singapore 2263
  47.  *        Republic of Singapore
  48.  *
  49.  ***************************************************************************/
  50.  
  51. #include <stdio.h>
  52. #include <stdlib.h>
  53. #include <string.h>
  54. #define mask8 255
  55.  
  56. unsigned char   *campg(a, b)              /* pointer to a & b array passed */
  57. unsigned char   *a, *b;
  58.  
  59. {
  60.    unsigned short   pterm, ma, mb, *pm, *pm1, *pm2, pos, pos1;
  61.    unsigned  long   m, k, count, count1, topow();
  62.    register  long   i, wo, wi;
  63.    register  char   j;
  64.          char   test;
  65.    unsigned  char   adjacency();
  66.    unsigned  char   *c, *c1, *d, *e, *s, *temp, adj0, adji;
  67.    unsigned  char   n, adj, nspm, cover, countb, countc;
  68.    unsigned  char   *adjacent(), *reduce(), *cpt(), *ssm(), adj_of_mi();
  69.  
  70.  
  71.    mb = *(b+2)<<8 | *(b+1);            /* no. of minterms in b-array */
  72.  
  73.    n    = *a;                          /* no. of variables */
  74.    nspm = *(a+3);                      /* no. of bytes/minterm */
  75.    ma = *(a+2)<<8 | *(a+1);            /* no. of minterms in a-array */
  76.  
  77.    temp = (unsigned char *) malloc(nspm+1);        /* temporary storage */
  78.    if (temp == 0)
  79.       {
  80.      printf("Out of memory -- CAMPG, *temp\n");
  81.      printf("Program terminated - 1\n");
  82.      exit(0);
  83.       }
  84.  
  85.    s = (unsigned char *) malloc(4);                /* header of s-array */
  86.    if (s == 0)
  87.       {
  88.      printf("Out of memory -- CAMPG, *s\n");
  89.      printf("Program terminated - 2\n");
  90.      exit(0);
  91.       }
  92.  
  93.    pterm = 0;                                /* no. of product term */
  94.  
  95.    /***
  96.     ***  MINIMIZE ALL MINTERMS WITH ADJACENCY OF 0 & 1 FIRST
  97.     ***/
  98.  
  99.    for (i=0; i<mb; i++)                      /* for adj = 0 or 1 */
  100.       {
  101.      *b = n;                             /* assign back to n */
  102.  
  103.      memcpy(temp, (b+4+nspm*i), nspm);   /* pick a minterm from b-array */
  104.      c = adjacent(temp, a, 1);           /* obtain the adjacent terms */
  105.      adj = *(c+1);                       /* adjacency of minterm */
  106.  
  107.      if (adj <= 1)                       /* adjacency 0 or 1 */
  108.         {
  109.            d = cpt(c);                   /* generate CPT */
  110.  
  111.            s = (unsigned char *) realloc(s,4+n*(pterm+1));   /* more space */
  112.            if (s == 0)
  113.           {
  114.              printf("Out of memory -- CAMPG, *s\n");
  115.              printf("Program terminated - 3\n");
  116.              exit(0);
  117.           }
  118.            memcpy ((s+4+n*pterm),d,n);   /* add CPT to soln array */
  119.            pterm++;                      /* product term count */
  120.  
  121.            b = reduce(c,b,i);            /* remove minterms covered from b-array */
  122.            i = (char) *b;                /* index pointer of b-array */
  123.            mb = *(b+2)<<8 | *(b+1);      /* value of mb altered in b-array */
  124.  
  125.            free(d);                    /* free pointer */
  126.         }
  127.      free(c);                            /* free pointer */
  128.       }
  129.  
  130.     /***
  131.      ***  MINIMIZE MINTERMS WITH ADJACENCY GREATER THAN 1
  132.      ***/
  133.  
  134.     while (mb > 0)
  135.        {
  136.       adj0 = 255;                     /* max for 8-bit */
  137.  
  138.       *b = n;                         /* assign back to n */
  139.  
  140.       /***
  141.        ***  OBTAIN AN ARRAY, PM OF POSITION OF ADJACENT TERMS WITH THE LOWEST
  142.        ***  ADJACENCY WRT B-ARRAY
  143.        ***/
  144.  
  145.       for (i=0; i<mb; i++)
  146.          {
  147.         memcpy(temp, (b+4+nspm*i), nspm);    /* pick a minterm */
  148.         adji = adjacency(temp, b);           /* adj wrt b-array */
  149.  
  150.         if (adji<adj0)                       /* look for lowest adj */
  151.            {
  152.               if (adj0!=255)                 /* not the 1st term */
  153.              free(pm);
  154.  
  155.               adj0 = adji;                   /* update lowest adj */
  156.               count = 1;                        /* set count to 1 */
  157.               pm = (unsigned short *) malloc(2);   /* space for pos */
  158.               if (pm == 0)
  159.              {
  160.                 printf("Out of memory -- CAMPG, *pm\n");
  161.                 printf("Program terminated - 4\n");
  162.                 exit(0);
  163.              }
  164.               *pm = i;                       /* 1st pos of minterm */
  165.            }
  166.  
  167.         else if (adji==adj0)                 /* adjacency as low */
  168.            {
  169.               count++;                       /* no. of elements in pm-array */
  170.               pm = (unsigned short*) realloc(pm, 2*count);    /* more space */
  171.               if (pm == 0)
  172.              {
  173.                 printf("Out of memory -- CAMPG, *pm\n");
  174.                 printf("Program terminated - 5\n");
  175.                 exit(0);
  176.              }
  177.               *(pm+count-1) = i;             /* elements in pm-array */
  178.            }
  179.          }
  180.  
  181.       if (count==1)                  /* if only 1 element in pm-array */
  182.          pos = *pm;
  183.       else
  184.          {
  185.         /***
  186.          ***  FORM PM-ARRAY, SELECT THE 1ST ADJACENT TERM THAT HAS THE
  187.          ***  LOWEST ADJACENCY WRT A-ARRAY
  188.          ***/
  189.  
  190.         adj0 = 255;                      /* max for 8-bit */
  191.         for (i=0; i<count; i++)          /* do for all in pm-array */
  192.            {
  193.               memcpy(temp, (b+4+nspm*(*(pm+i))), nspm);
  194.               adji = adjacency(temp, a);          /* adj wrt a-array */
  195.  
  196.               if (adji<adj0)                      /* new lowest found */
  197.              {
  198.                 adj0 = adji;                  /* update lowest */
  199.                 pos = *(pm+i);                /* position of required minterm */
  200.              }
  201.            }
  202.          }
  203.        free(pm);
  204.  
  205.        memcpy(temp, (b+4+nspm*pos), nspm);       /* pick the required minterm */
  206.  
  207.        /***
  208.         ***  GENERATE SSM AND TEST FOR COVERAGE BY FUNCTION
  209.         ***/
  210.  
  211.        c = adjacent(temp, a, 255);          /* obtain adjacent terms */
  212.        adj = *(c+1);                        /* adjacency of minterms */
  213.        d = cpt(c);                          /* generate CPT */
  214.        e = ssm(d);                          /* generate SSM */
  215.        m = topow(*(e+1));                   /* no. of SSM terms */
  216.  
  217.        for (j=0; j<m; j++)                  /* check for SSM coverage */
  218.           {
  219.          memcpy (temp, (e+4+nspm*j), nspm);
  220.          test = exist (temp, a, ma);
  221.          if (test == -1)                /* SSM term not in a-array */
  222.              break;
  223.           }
  224.  
  225.        /***
  226.         ***  ALL SSM COVERED BY THE FUNCTION, SELECT CPT AS PRODUCT TERM
  227.         ***/
  228.  
  229.        if (test == 0)                       /* all SSM's covered by fn */
  230.           {
  231.          if (m > 65536)                 /* too many SSM terms */
  232.             {
  233.                printf("Product Term Too Huge \n");
  234.                printf("Program terminated \n");
  235.                exit(0);
  236.             }
  237.          *(e+1) = (m-1) & mask8;        /* no. of SSM terms minus 1 */
  238.          *(e+2) = (m-1)>>8 & mask8;
  239.          b = reduce(e,b,i);             /* reduce minterms covered from b-array */
  240.          mb = *(b+2)<<8 | *(b+1);       /* no. of minterms in b-array */
  241.  
  242.          s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
  243.          if (s == 0)
  244.             {
  245.                printf("Out of memory -- CAMPG, *s\n");
  246.                printf("Program terminated - 6\n");
  247.                exit(0);
  248.             }
  249.          memcpy((s+4+n*pterm),d,n);     /* add CPT to soln array */
  250.          pterm++;                       /* no. of product terms */
  251.  
  252.          free(d);                       /* free pointers */
  253.          free(e);
  254.           }
  255.        else
  256.           {
  257.          /***
  258.           ***  SSM NOT COVERED BY THE FUNCTION
  259.           ***/
  260.  
  261.          free(d);                       /* free pointer */
  262.          cover =0;                      /* coverage status */
  263.  
  264.          while (!cover)        /* do until shrinked SSM is covered */
  265.             {
  266.                /***
  267.             ***  OBTAIN AN ARRAY, PM OF POSITIONS OF ADJACENT TERMS, MI WITH THE LARGEST WI
  268.             ***/
  269.  
  270.                wo = -1;                        /* initial value */
  271.                for (j=0; j<adj; j++)           /* do for all adjacent terms */
  272.               {
  273.                  memcpy(temp,(c+4+nspm*(j+1)),nspm); /* pick adjacent term */
  274.  
  275.                  wi = adj_of_mi(temp,e,a);           /* obtain wi */
  276.                  if (wi>wo)
  277.                 {
  278.                    if (wo != -1)                 /* not the first */
  279.                       free(pm);
  280.                    wo = wi;                      /* new lowest value */
  281.                    count = 1;                    /* reset count to 1 */
  282.  
  283.                    pm = (unsigned short *) malloc(2);  /* space for pm */
  284.                    if (pm==0)
  285.                       {
  286.                      printf("Out of memory -- CAMPG, *pm\n");
  287.                      printf("Program terminated - 7\n");
  288.                      exit(0);
  289.                       }
  290.                    *pm = j;                      /* first element */
  291.                 }
  292.                  else if (wi==wo)                    /* wi as large */
  293.                 {
  294.                    count++;                      /* no. of element in pm-array */
  295.  
  296.                    pm = (unsigned short *) realloc (pm, 2*count);  /* more space */
  297.                    if (pm==0)
  298.                       {
  299.                      printf("Out of memory -- CAMPG, *pm\n");
  300.                      printf("Program terminated - 8\n");
  301.                      exit(0);
  302.                       }
  303.                    *(pm+count-1) = j;            /* elements of pm-array */
  304.                 }
  305.               }
  306.                free(e);                                  /* free pointer */
  307.  
  308.                /***
  309.             ***  DETERMINE FROM PM-ARRAY, AN ARRAY, PM1 OF POSITION OF ADJACENT TERMS
  310.             ***  THAT HAVE ALREADY BEEN COVERED
  311.             ***/
  312.  
  313.                pm1 = (unsigned short *) malloc(2);       /* space for pm1 */
  314.                if (pm1==0)
  315.               {
  316.                  printf("Out of memory -- CAMPG, *pm1\n");
  317.                  printf("Program terminated - 9\n");
  318.                  exit(0);
  319.               }
  320.  
  321.                k = 0;
  322.                for (j=0; j<count; j++)              /* do for all element in pm-array */
  323.               {
  324.                  memcpy(temp, (c+4+nspm*(1+ *(pm+j))), nspm);    /* pick adj term */
  325.                  test = exist(temp,b,mb);
  326.                  if (test == -1)                               /* already covered */
  327.                 {
  328.                    memcpy((pm1+k++), (pm+j), 2);       /* transfer pos to pm1 */
  329.  
  330.                    pm1 = (unsigned short *) realloc(pm1, 2*(k+1)); /*  more space */
  331.                    if (pm1==0)
  332.                       {
  333.                      printf("Out of memory -- CAMPG, *pm1\n");
  334.                      printf("Program terminated - 10\n");
  335.                      exit(0);
  336.                       }
  337.                 }
  338.               }
  339.  
  340.                /***
  341.             ***  OBTAIN FROM PM1-ARRAY, AN ARRAY PM2 OF ADJACENT TERMS, MI WITH
  342.             ***  THE LOWEST ADJACENCY WRT B-ARRAY
  343.             ***/
  344.  
  345.                if (k != 0)                              /* some elements in pm1 */
  346.               {
  347.                  pm2 = (unsigned short *) malloc(2*k);     /* space for pm2 */
  348.                  if (pm2==0)
  349.                 {
  350.                    printf("Out of memory -- CAMPG, *pm2\n");
  351.                    printf("Program terminated - 11\n");
  352.                    exit(0);
  353.                 }
  354.  
  355.                  adj0 = 255;                               /* max of 8-bit */
  356.                  for (j=0; j<k; j++)          /* all elements in pm1-array */
  357.                 {
  358.                    memcpy(temp, (c+4+nspm*(1+*(pm1+j))),nspm);  /* pick adj term */
  359.                    adji = adjacency(temp,b);                  /* adj wrt b-array */
  360.  
  361.                    if (adji<adj0)                              /* new lowest adj */
  362.                       {
  363.                      count1 = 1;                           /* no. in pm2-array */
  364.                      adj0 = adji;                          /* update lowest */
  365.                      *pm2 = *(pm1+j);                      /* element in pm2 */
  366.                       }
  367.                    else if (adji==adj0)                        /* adj as small */
  368.                       {
  369.                      count1++;                             /* no. in pm2-array */
  370.                      *(pm2+count1-1) = *(pm1+j);           /* element in pm2 */
  371.                       }
  372.                 }
  373.                  free(pm1);                    /* free pointer */
  374.  
  375.                  if (count1 == 1)              /* only 1 element in pm2-array */
  376.                 pos = *pm2;                /* position of required adj term */
  377.                  else
  378.                 {
  379.                    /***
  380.                     ***   SHRINK CPT, TAKING EACH OF THE CORRESPONDING ADJACENT
  381.                     ***   TERMS IN PM2-ARRAY AND TAKE THE ONE WHOSE SHRINKED CPT
  382.                     ***   COVERS MOST OF THE TERMS IN B-ARRAY
  383.                     ***/
  384.  
  385.                    countc = 0;                      /* lowest value */
  386.  
  387.                    c1 = (unsigned char *) malloc(4+(*(c+1)+1)*nspm);  /* space for adj terms */
  388.                    if (c1==0)
  389.                       {
  390.                      printf("Out of memory -- CAMPG, *c1\n");
  391.                      printf("Program terminated - 12\n");
  392.                      exit(0);
  393.                       }
  394.  
  395.                    for (j=0; j<count1; j++)             /* all elements in pm2-array */
  396.                       {
  397.                      memcpy(c1, c, 4+nspm*(1+ *(c+1)));         /* pick adj term */
  398.                      *(c1+1) = *(c+1)-1;                  /* decrement adjacency */
  399.  
  400.                      pos1 = *(pm2+j);                     /* adj term to shrink in turn */
  401.                      memcpy ((c1+4+nspm*(1+pos1)), (c1+4+nspm*(2+pos1)), nspm*(*(c1+1)-pos1));
  402.  
  403.                      d = cpt(c1);                         /* generate shrinked CPT */
  404.                      e = ssm(d);                          /* generate shrinked SSM */
  405.                      m = topow (*(e+1));                  /* no. of SSM terms */
  406.  
  407.                      countb = 0;                          /* reset counter */
  408.  
  409.                      for (i=0; i<m; i++)                  /* do for all SSM's in e-array */
  410.                         {
  411.                            memcpy(temp, (e+4+nspm*i), nspm);   /* pick SSM term */
  412.                            test = exist(temp, b, mb);
  413.                            if (test==0)                        /* still in b-array */
  414.                           countb++;                        /* coverage count */
  415.                         }
  416.  
  417.                      if (countb>=countc)             /* largest count found */
  418.                         {
  419.                            countc = countb;          /* update largest count */
  420.                            pos = pos1;               /* required pos of adj term */
  421.                         }
  422.                      free(d);                /* free pointers */
  423.                      free(e);
  424.                       }
  425.                    free(c1);           /* free pointer */
  426.                 }
  427.                  free(pm2);                /* free pointer */
  428.               }
  429.                else                            /* non in pm1-array */
  430.               {
  431.                  /***
  432.                   ***  ALL TERMS IN PM-ARRAY HAS NOT BEEN COVERED, SELECT ONE
  433.                   ***  WITH THE LOWEST ADJACENCY WRT B-ARRAY
  434.                   ***/
  435.  
  436.                  adj0 = 255;                /* max for 8-bit */
  437.                  for (j=0; j<count; j++)    /* all in pm-aaray */
  438.                 {
  439.                    memcpy(temp, (c+4+nspm*(1+ *(pm+j))), nspm);  /* pick adj term */
  440.                    adji = adjacency(temp, b);                    /* adj wrt b-array */
  441.  
  442.                    if (adji<adj0)              /* lowest adj found */
  443.                       {
  444.                      adj0 = adji;          /* update lowest */
  445.                      pos = *(pm+j);        /* required position of adj term */
  446.                       }
  447.                 }
  448.               }
  449.                free(pm);                 /* free pointer */
  450.  
  451.                adj--;                    /* no. of adj term after shrinking */
  452.                *(c+1) = adj;             /* adjacency after shrinking */
  453.  
  454.                /***
  455.             ***  SHRINK CPT (REMOVE THE SELECTED ADJACENT TERM FROM C-ARRAY),
  456.             ***  GENERATE NEW CPT, SSM AND TEST FOR COVERAGE BY FUNCTION
  457.             ***/
  458.  
  459.                memcpy((c+4+nspm*(1+pos)), (c+4+nspm*(2+pos)), nspm*(adj-pos));  /* shrink CPT */
  460.  
  461.                c = (unsigned char*) realloc(c, 4+nspm*(1+adj));   /* reduce space */
  462.                if (c==0)
  463.               {
  464.                  printf("Out of memory -- CAMPG, *c\n");
  465.                  printf("Program terminated - 13\n");
  466.                  exit(0);
  467.               }
  468.  
  469.                d = cpt(c);                  /* generate CPT */
  470.                e = ssm(d);                  /* generate SSM */
  471.                m = topow(*(e+1));           /* no. of SSM terms */
  472.  
  473.                for (i=0; i<m; i++)          /* check SSM coverage by function */
  474.               {
  475.                  memcpy(temp, (e+4+nspm*i), nspm);  /* pick SSM term */
  476.                  test = exist(temp,a,ma);
  477.                  if (test == -1)                    /* SSM term not covered */
  478.                 break;
  479.               }
  480.  
  481.                /***
  482.             ***  SHRINKED SSM COVERED BY FUNCTION, REDUCE B-ARRAY
  483.             ***  AND SELECT SHRINKED CPT AS PRODUCT TERM
  484.             ***/
  485.  
  486.                if (test==0)                   /* SSM covered */
  487.               {
  488.                  if (m > 65536)                  /* too many SSM terms */
  489.                 {
  490.                    printf("Product Term Too Huge \n");
  491.                    printf("Program terminated \n");
  492.                    exit(0);
  493.                 }
  494.                  *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  495.                  *(e+2) = (m-1)>>8 & mask8;
  496.                  b = reduce(e, b, i);     /* remove minterms covered from b-array */
  497.                  mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
  498.  
  499.                  s = (unsigned char *) realloc(s, 4+n*(pterm+1));  /* more space */
  500.                  if (s==0)
  501.                 {
  502.                    printf("Out of memory -- CAMPG, *s\n");
  503.                    printf("Program terminated - 14\n");
  504.                    exit(0);
  505.                 }
  506.                  memcpy ((s+4+n*pterm), d, n);      /* add shrinked CPT to soln array */
  507.                  pterm++;                           /* no. of product terms */
  508.  
  509.                  cover = 1;                         /* coverage status */
  510.                  free(e);                           /* free pointer */
  511.               }
  512.                free (d);                      /* free pointer */
  513.             }
  514.           }
  515.       free(c);                   /* free pointer */
  516.       }
  517.    *s = n;                           /* no. of variables */
  518.    *(s+1) = pterm & mask8;           /* no. of product terms in 2 bytes */
  519.    *(s+2) = pterm>>8 & mask8;
  520.  
  521.    free(temp);                       /* free pointer */
  522.    free(a);
  523.    free(b);
  524.  
  525.    return(s);                        /* return solution array */
  526. }
  527.  
  528.